package com.example.demo.leetcode;

/**
 * https://leetcode.cn/problems/search-a-2d-matrix-ii/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/07 11:14
 */
public class _240_搜索二维矩阵Ⅱ {

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        boolean b = searchMatrix2(matrix, 20);
        System.out.println(b);

    }

    /**
     * 方法一：暴力求解
     * <p>
     * 时间复杂度：O(m*n), m为二维数组的行数，n为二维数组的列数
     * <p>
     * 空间复杂度：O(1)
     *
     * @param matrix 二维数组
     * @param target 目标值
     * @return {@link boolean}
     * @author WangYX
     * @date `2024/03/07` 11:18
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for (int[] ints : matrix) {
            for (int j = 0; j < n; j++) {
                if (ints[j] > target) {
                    break;
                }
                if (ints[j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方法二：二分查找
     * <p>
     * 由于数组：
     * <p>
     * 每行的元素从左到右升序排列。
     * <p>
     * 每列的元素从上到下升序排列。
     * <p>
     * 所以可以根据二维数组中每个数组使用二分查找确定目标值所在
     * <p>
     * <p>
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     *
     * @param matrix 二维数组
     * @param target 目标值
     * @return {@link boolean}
     * @author WangYX
     * @date `2024/03/07` 11:18
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            if (ints[0] > target || ints[ints.length - 1] < target) {
                continue;
            }
            if (ints[0] == target || ints[ints.length - 1] == target) {
                return true;
            }
            if (binarySearch(ints, target)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 二分查找算法
     * <p>
     * low = 0 <br>
     * high = arr.length -1 <br>
     * mid = ((high-low)>>>1)+low <br>
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     *
     * @param arr
     * @param target
     * @return {@link boolean}
     * @author WangYX
     * @date 2024/03/07 11:44
     */
    public static boolean binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = ((high - low) >>> 1) + low;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            }
        }
        return false;
    }

}
